<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>1974：[Sdoi2010]auction 代码拍卖会</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Sdoi2010]auction 代码拍卖会</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Sdoi2010]auction 代码拍卖会</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Sdoi2010]auction 代码拍卖会                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：64MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p>随着iPig在P++语言上的造诣日益提升，他形成了自己一套完整的代<br />
码库。猪王国想参加POI的童鞋们都争先恐后问iPig索要代码库。iPi<br />
g不想把代码库给所有想要的小猪，只想给其中的一部分既关系好又<br />
肯出钱的小猪，于是他决定举行了一个超大型拍卖会。 在拍卖会上<br />
，所有的N头小猪将会按照和iPig的好感度从低到高，从左到右地在i<br />
Pig面前站成一排。每个小猪身上都有9猪币（与人民币汇率不明），<br />
从最左边开始，每个小猪依次举起一块牌子，上面写上想付出的买代<br />
码库的猪币数量（1到9之间的一个整数）。大家都知道，如果自己付<br />
的钱比左边的猪少，肯定得不到梦寐以求的代码库，因此从第二只起<br />
，每只猪出的钱都大于等于左边猪出的价钱。最终出的钱最多的小猪<br />
（们）会得到iPig的代码库真传，向着保送PKU（Pig Kingdom Unive<br />
rsity）的梦想前进。 iPig对自己想到的这个点子感到十分满意，在<br />
去现场的路上，iPig就在想象拍卖会上会出现的场景，例如一共会出<br />
现多少种出价情况之类的问题，但这些问题都太简单了，iPig早已不<br />
敢兴趣了，他想要去研究更加困难的问题。iPig发现如果他从台上往<br />
下看，所有小猪举的牌子从左到右将会正好构成一个N位的整数，他<br />
现在想要挑战的问题是所有可能构成的整数中能正好被P整除的有多<br />
少个。由于答案过大，他只想要知道答案mod 999911659就行了。 </p></p><hr/><h3>输入格式</h3><p><p>一行：两个数N（1&le;N&le;10^18）、P(1&le;P&le;500)，用一个空格分开。</p></p><hr/><h3>输出格式</h3><p><p>一行：一个数，表示答案除以999911659的余数。</p></p><hr/><h3>样例输入</h3><pre>2 3
</pre><hr/><h3>样例输出</h3><pre>15
样例解释
方案可以是：12 15 18 24 27 33 36 39 45 48 57 66 69 78 99，共15种。
数据规模
测试点	N	P	测试点	N	P
1	≤1000	≤500	6	≤10^6	≤500
2	≤10^18	5	7	≤10^18	≤120
3	≤10^18	≤10	8	≤10^18	≤500
4	≤10^18	≤10	9	≤10^18	≤500
5	≤10^18	25	10	≤10^18	≤500
</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Sdoi2010 Contest2 Day2</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=1974" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1974" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>